package pl.poznan.put.cs.to.tsp.common;

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class Vertexes {
	private int[] x;
	private int[] y;
	private int maxIndex;
	private int actualIndex;
	private int[][] distanceMatrix;
	private LinkedList<Integer>[] closestVertexesArray;
	private int maxDistance;
	private int[] candidateArray;

	@SuppressWarnings("unchecked")
	public Vertexes(int length) {
		this.x = new int[length];
		this.y = new int[length];
		this.maxIndex = length - 1;
		this.actualIndex = 0;
		this.distanceMatrix = new int[length][length];
		this.closestVertexesArray = new LinkedList[length];
		this.candidateArray = new int[length];
	}

	public final void add(int x, int y) {
		if (this.actualIndex > this.maxIndex) {
			throw new RuntimeException("Maximum length exceeded!");
		}
		this.x[this.actualIndex] = x;
		this.y[this.actualIndex] = y;
		for (int i = 0; i < actualIndex; i++) {
			int distance = this.calculateDistanceBetween(i, actualIndex);
			this.distanceMatrix[i][actualIndex] = distance;
			this.distanceMatrix[actualIndex][i] = distance;
		}
		this.distanceMatrix[actualIndex][actualIndex] = 0;
		this.actualIndex++;
		if (this.actualIndex > this.maxIndex) {
			this.calculateClosestVertexes();
			this.calculateCandidates();
		}
	}

	private void calculateCandidates() {
		this.maxDistance = Integer.MIN_VALUE;
		for (int i = 0; i < this.closestVertexesArray.length; i++) {
			LinkedList<Integer> l = this.closestVertexesArray[i];
			int minimum = this.distanceMatrix[i][l.getFirst()];
			int maximum = this.distanceMatrix[i][l.getLast()];
			if (maximum > this.maxDistance) {
				this.maxDistance = maximum;
			}
			int candidateDistance = (int) Math.sqrt(maximum * minimum);
			for (int j = 0; j < l.size(); j++) {
				if (this.distanceMatrix[i][l.get(j)] > candidateDistance) {
					this.candidateArray[i] = j;
					break;
				}
			}
		}

	}

	private void calculateClosestVertexes() {
		for (int i = 0; i <= this.maxIndex; i++) {
			final int actual = i;
			LinkedList<Integer> closestVertexes = new LinkedList<Integer>();
			for (int j = 0; j <= this.maxIndex; j++) {
				if (i != j) {
					closestVertexes.add(j);
				}
			}
			Collections.sort(closestVertexes, new Comparator<Integer>() {
				@Override
				public int compare(Integer o1, Integer o2) {
					return distanceMatrix[actual][o1]
							- distanceMatrix[actual][o2];
				}
			});
			this.closestVertexesArray[i] = closestVertexes;
		}
	}

	public final int getX(int index) {
		return this.x[index];
	}

	public final int getY(int index) {
		return this.y[index];
	}

	private final int calculateDistanceBetween(int index1, int index2) {
		int dx = this.x[index1] - this.x[index2];
		int dy = this.y[index1] - this.y[index2];
		int square = dx * dx + dy * dy;
		return (int) (Math.sqrt(square) + 0.5);
	}

	public final int getDistanceBetween(int index1, int index2) {
		return this.distanceMatrix[index1][index2];
	}

	public final int getNumberOfNodes() {
		return this.maxIndex + 1;
	}

	public final int getMaxDistance() {
		return this.maxDistance;
	}

	public final LinkedList<Integer> getClosestVertexes(int i) {
		return this.closestVertexesArray[i];
	}

	public final List<Integer> getCandidateVertexes(int i) {
		return this.closestVertexesArray[i].subList(0, this.candidateArray[i]);
	}

	public final List<Integer> getClosestVertexes(int i, int length) {
		return this.closestVertexesArray[i].subList(0, length);
	}

}
